package com.stanley.alogrithm.dynamic;

public class Palindrome {

    public static void main(String[] args) {
        String input = "abc1234321ab";
        //String input = "cccccccc";
        int length = getLongestPalindrome(input);
        System.out.println("Longest: " + length);
    }

    public static int getLongestPalindrome(String s) {
        int n = s.length();
        int leftPivot = 0, rightPivot = 0;
        int longest = 1;
        int longestLeft = 0, longestRight = 0, longestPivot = 0;
        String target = "";
        for (leftPivot = 0; leftPivot <= n - 1; leftPivot++) {
            rightPivot = leftPivot;
            int len = 1;
            while (rightPivot + 1 < n && s.charAt(leftPivot) == s.charAt(rightPivot + 1)) {
                rightPivot++;
                len++;
            }
            int left = leftPivot;
            int right = rightPivot;
            while (left - 1 >= 0 && right + 1 < n && s.charAt(left - 1) == s.charAt(right + 1)) {
                len += 2;
                left--;
                right++;
            }
            if (len > longest) {
                longest = len;
                longestLeft = Math.max(left, 0);
                longestRight = Math.min(right, n - 1);
                longestPivot = leftPivot;
                target = s.substring(longestLeft, longestRight + 1);
            }
        }
        System.out.println(String.format("longestLeft=%d, longestRight=%d, longestPivot=%d", longestLeft, longestRight, longestPivot));
        System.out.println("matched str: " + target);

        return longest;
    }

    private void findPalindrome(int pivot, int left, int right) {

    }
}
